#include <vector>
using namespace std;
// 回溯
void backtrace(vector<int> &nums, int i, int target, bool &ok) {
  if (i == nums.size())
    return;
  if (target == 0) {
    ok = true;
    return;
  }
  for (int j = i + 1; j < nums.size(); ++j) {
    backtrace(nums, j, target - nums[j], ok);
    if (ok) {
      return;
    }
  }
}
bool canPartition(vector<int> &nums) {
  int target = 0;
  for (int x : nums) {
    target += x;
  }
  if (target % 2 == 1)
    return false;
  target = target / 2;
  bool ok = false;
  backtrace(nums, 0, target, ok);
  return ok;
}
// 动态规划： 层级遍历
bool canPartition_(vector<int> &nums) {
  int total = 0;
  for (int x : nums) {
    total += x;
  }
  if (total % 2 == 1)
    return false;
  int target = total / 2;
  vector<int> dp(target + 1, 0);
  // 边界条件
  dp[0] = true;
  for (auto num : nums) {
    vector<int> dp_tmp(dp);
    for (int i = 0; i <= target; ++i) {
      if (dp[i] && i + num <= target)
        dp_tmp[i + num] = dp_tmp[i];
    }
    dp = dp_tmp;
    if (dp[target] == true)
      return true;
  }
  return false;
}